﻿#include <iostream>
using namespace std;
#include <vector>
#include <list>
#include <queue>
//
//
//// 等差数列划分
////https://leetcode.cn/problems/arithmetic-slices/
//class Solution {
//public:
//    int numberOfArithmeticSlices(vector<int>& nums)
//    {
//        int n = nums.size();
//        vector<int> dp(n + 1);
//        int ret = 0;
//        for (int i = 2; i < n; i++)
//        {
//            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
//            {
//                dp[i] = dp[i - 1] + 1;
//            }
//            ret += dp[i];
//        }
//        return ret;
//    }
//};
//
//// 最长流子数组
//// https://leetcode.cn/problems/longest-turbulent-subarray/
//class Solution
//{
//public:
//    int maxTurbulenceSize(vector<int>& arr)
//    {
//        int n = arr.size();
//        vector<int> f(n, 1);
//        vector<int> g(n, 1);
//        int Max = 1;
//        for (int i = 1; i < n; i++)
//        {
//            if (arr[i - 1] < arr[i])
//            {
//                f[i] = g[i - 1] + 1;
//            }
//            else if (arr[i - 1] > arr[i])
//            {
//                g[i] = f[i - 1] + 1;
//            }
//            Max = max(Max, max(g[i], f[i]));
//        }
//        return Max;
//
//    }
//};
//
//
//class Solution
//{
//public:
//    void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
//    {
//        dfs(a, b, c, a.size());
//    }
//    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
//    {
//        if (n == 1)
//        {
//            c.push_back(a.back());
//            a.pop_back();
//            return;
//        }
//        dfs(a, c, b, n - 1);
//        c.push_back(a.back());
//        a.pop_back();
//        dfs(b, a, c, n - 1);
//    }
//};
//
//
//
//// 单词拆分
//// https://leetcode.cn/problems/word-break/
//class Solution
//{
//public:
//    bool wordBreak(string s, vector<string>& wordDict)
//    {
//        int n = s.size();
//        vector<bool> dp(n + 1);
//        dp[0] = true;
//        string s1;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = i; j >= 1; j--)
//            {
//                s1.clear();
//                s1 = s.substr(j - 1, i - j + 1);
//                int flag = 0;
//                for (int k = 0; k < wordDict.size(); k++)
//                {
//                    if (s1 == wordDict[k])
//                    {
//                        flag = 1;
//                    }
//                }
//                if (dp[j - 1] && flag)
//                {
//                    dp[i] = true;
//                    break;
//                }
//            }
//        }
//        return dp[n];
//
//    }
//};

#include <set>
//int main()
//{
//	int n;
//	int m;
//	cin >> n;
//	list<int> l;
//	set<int> s;
//	//priority_queue<int> pq;
//	//int size;
//	int Max = INT_MIN;                         
//	while (n--)
//	{
//		cin >> m;
//		if (m == 0)
//		{
//			int x;
//			cin >> x;
//			l.push_back(x);
//			s.insert(x);
//			//pq.push(x);
//		}
//		else if (m == 1 && l.size())
//		{
//			int t = l.back();
//			l.pop_back();
//			s.erase(t);
//			//pq.pop();
//		}
//		else if(m == 2)
//		{
//			if (l.size() == 0)
//			{
//				cout << 0 << endl;
//			}
//			else
//			{
//				set<int>::reverse_iterator it = s.rbegin();
//				cout << *it << endl;
//				/*for (auto e : l)
//				{
//					Max = max(e, Max);
//				}
//				cout << Max << endl;
//				Max = INT_MIN;*/
//				//cout << pq.top() << endl;
//			}
//			
//		}
//	}
//	return 0;
//}


//class Solution
//{
//	vector<int> ret;
//	vector<int> index; // 记录 nums 中当前元素的原始下标
//	int tmpNums[500010];
//	int tmpIndex[500010];
//public:
//	vector<int> countSmaller(vector<int>& nums)
//	{
//		int n = nums.size();
//		ret.resize(n);
//		index.resize(n);
//		// 初始化⼀下 index 数组
//		for (int i = 0; i < n; i++)
//			index[i] = i;
//		mergeSort(nums, 0, n - 1);
//		return ret;
//	}
//
//	void mergeSort(vector<int>& nums, int left, int right)
//	{
//		if (left >= right) return;
//		// 1. 根据中间元素，划分区间
//		int mid = (left + right) >> 1;
//		// [left, mid] [mid + 1, right]
//		// 2. 先处理左右两部分
//		mergeSort(nums, left, mid);
//		mergeSort(nums, mid + 1, right);
//		// 3. 处理⼀左⼀右的情况
//		int cur1 = left, cur2 = mid + 1, i = 0;
//		while (cur1 <= mid && cur2 <= right) // 降序
//		{
//			if (nums[cur1] <= nums[cur2])
//			{
//				tmpNums[i] = nums[cur2];
//				tmpIndex[i++] = index[cur2++];
//			}
//			else
//			{
//				ret[index[cur1]] += right - cur2 + 1; // 重点
//				tmpNums[i] = nums[cur1];
//				tmpIndex[i++] = index[cur1++];
//			}
//		}
//		// 4. 处理剩下的排序过程
//		while (cur1 <= mid)
//		{
//			tmpNums[i] = nums[cur1];
//			tmpIndex[i++] = index[cur1++];
//		}
//		while (cur2 <= right)
//		{
//			tmpNums[i] = nums[cur2];
//			tmpIndex[i++] = index[cur2++];
//		}
//		for (int j = left; j <= right; j++)
//		{
//			nums[j] = tmpNums[j - left];
//			index[j] = tmpIndex[j - left];
//		}
//	}
//};


//int main()
//{
//	vector<string> s;
//	string s1;
//	char ch;
//	cin >> ch;
//	cin >> s1;
//	while (s1[0] != '$')
//	{
//		cin >> s1;
//		if (s1[0] == '#')
//		{
//			s.push_back(s1);
//		}
//		else if (s1[0] == '+')
//		{
//			s.push_back(s1);
//		}
//		else
//		{
//			for (int i = 0; i < s.size(); i++)
//			{
//				s[i] == s1;
//			}
//		}
//	}
//	return 0;
//}



//map<string, string>fa;//map类型的定义：注意没有空格 
//string now, father;
//string find(string x)//路径压缩函数 
//{
//	if (x == fa[x])
//		return x;
//	else
//		return fa[x] = find(fa[x]);
//}
//int main()
//{
//	char relation;//确定关系的字符 
//	cin >> relation;
//	while (relation != '$')//如果输入文件有效
//	{
//		cin >> now;
//		getchar();//非常重要！！！不写这句话读进来的名字就有一个换行符 
//		if (relation == '#')
//		{
//			father = now;
//			if (fa[now] == "")
//				fa[now] = now;//如果刚读入的是一个父亲关系且他还没有父亲，就让他自己当自己的父亲 
//		}
//		else if (relation == '+')
//		{
//			fa[now] = father;//如果刚读入的是一个儿子关系,就加入到图里面 
//		}
//		else
//		{
//			cout << now << ' ' << find(now) << endl;//如果是要问询祖先，就按照要求输出
//		}
//		cin >> relation;//读入下一个关系 
//	}
//	return 0;
//}


// 洛谷P2814
#include <map>
//map<string, string> str;
//string find(string x)
//{
//	if (str[x] == x)
//	{
//		return x;
//	}
//	else
//		return str[x] = find(str[x]);
//}
//int main()
//{
//	string s;
//	string f;
//	char ch;
//	cin >> ch;
//	cin >> s;
//	while (ch != '$')
//	{
//		//cin >> s;
//		if (ch == '#')
//		{
//			f = s;
//			if (str[s] == "")
//			{
//				str[s] = s;
//			}
//		}
//		else if (ch == '+')
//		{
//			str[s] = f;
//		}
//		else if (ch == '?')
//		{
//			cout << s << ' ' << find(s) << endl;
//		}
//		cin >> ch;
//		cin >> s;
//	}
//	return 0;
//}


//洛谷3367
//int a[10005];
//int find(int k)
//{
//	if (a[k] == k)
//	{
//		return k;
//	}
//	return a[k] = find(a[k]);
//}
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		a[i] = i;
//	}
//	while (m--)
//	{
//		int z, x, y;
//		cin >> z >> x >> y;
//		if (z == 1)
//		{
//			//让y的父亲成为x的父亲
//			a[find(x)] = find(y);
//
//		}
//		else
//		{
//			if (find(x) == find(y))
//			{
//				cout << 'Y' << endl;
//			}
//			else
//			{
//				cout << 'N' << endl;
//			}
//		}
//	}
//	return 0;
//}



// 洛谷p2021
queue<int>a;
int sc[1000005], ans[1000005];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        a.push(i);//先制造一叠牌(1,2,...,n)
    for (int i = 1; !a.empty(); i++)//开始模拟
    {
        a.push(a.front());
        a.pop();
        sc[i] = a.front();
        a.pop();
    }
    for (int i = 1; i <= n; i++)//将i放在sc[i]处，经过一通操作后，就在正确的位置了
        ans[sc[i]] = i;
    for (int i = 1; i <= n; i++)//输出
        cout << ans[i] << " ";
    return 0;
}


class Solution
{
public:
    int findSubstringInWraproundString(string s)
    {
        int n = s.size();
        if (n == 1)
        {
            return 1;
        }
        vector<int> dp(n, 1);
        vector<int> hash(26);
        for (int i = 1; i < n; i++)
        {
            if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a'))
            {
                dp[i] = dp[i - 1] + 1;
            }
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }
        for (int i = 0; i < 26; i++)
        {
            ret += hash[i];
        }
        return ret;
    }
};


// 摆动序列
// https://leetcode.cn/problems/wiggle-subsequence/
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1, 1);
        vector<int> g(n + 1, 1);
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    f[i] = max(g[j] + 1, f[i]);
                }
                else if (nums[i] < nums[j])
                {
                    g[i] = max(f[j] + 1, g[i]);
                }
            }
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};



// 最长递增子序列
// https://leetcode.cn/problems/longest-increasing-subsequence/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
                ret = max(ret, dp[i]);
            }
        }
        return ret;

    }
};



class Solution
{
public:
    int findNumberOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> len(n, 1), count(n, 1); // 1. 创建 dp 表 + 初始化
        int retlen = 1, retcount = 1; // 记录最终结果
        for (int i = 1; i < n; i++) // 2. 填表
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    if (len[j] + 1 == len[i])
                        count[i] += count[j];
                    else if (len[j] + 1 > len[i]) // 重新计数
                        len[i] = len[j] + 1, count[i] = count[j];
                }
            }
            if (retlen == len[i])
                retcount += count[i];
            else if (retlen < len[i]) // 重新计数
                retlen = len[i], retcount = count[i];
        }
        // 3. 返回结果
        return retcount;
    }
};




// N叉树的层序遍历
// https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
//class Solution {
//public:
//    vector<vector<int>> levelOrder(Node* root)
//    {
//        vector<vector<int>> ret;
//        queue<Node*> q;
//        if (root == nullptr) return ret;
//        q.push(root);
//        while (q.size())
//        {
//            int sz = q.size();
//            vector<int> tmp;
//            for (int i = 0; i < sz; i++)
//            {
//                Node* t = q.front();
//                q.pop();
//                tmp.push_back(t->val);
//                for (Node* child : t->children)
//                {
//                    if (child != nullptr)
//                    {
//                        q.push(child);
//                    }
//                }
//            }
//            ret.push_back(tmp);
//        }
//        return ret;
//
//    }
//};


// 二叉树的锯齿遍历
// https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
//class Solution {
//public:
//    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
//    {
//        vector<vector<int>> ret;
//        queue<TreeNode*> q;
//        if (root == nullptr) return ret;
//        q.push(root);
//        int count = 1;
//        while (q.size())
//        {
//            int sz = q.size();
//            vector<int> tmp;
//            for (int i = 0; i < sz; i++)
//            {
//                TreeNode* t = q.front();
//                q.pop();
//                tmp.push_back(t->val);
//                if (t->left)
//                {
//                    q.push(t->left);
//                }
//                if (t->right)
//                {
//                    q.push(t->right);
//                }
//            }
//            if (count % 2 == 0)
//            {
//                reverse(tmp.begin(), tmp.end());
//            }
//            ret.push_back(tmp);
//            count++;
//
//        }
//        return ret;
//    }
//};



// 二叉树最长宽度
// https://leetcode.cn/problems/maximum-width-of-binary-tree/
//class Solution {
//public:
//    int widthOfBinaryTree(TreeNode* root)
//    {
//        vector<pair<TreeNode*, unsigned int>> q;
//        q.push_back({ root, 1 });
//        unsigned int ret = 0;
//        while (q.size())
//        {
//            TreeNode* t1 = q.front().first;
//            unsigned pos1 = q.front().second;
//            TreeNode* t2 = q.back().first;
//            unsigned pos2 = q.back().second;
//            ret = max(ret, pos2 - pos1 + 1);
//
//            vector<pair<TreeNode*, unsigned int>> tmp;
//            for (int i = 0; i < q.size(); i++)
//            {
//                if (q[i].first->left)
//                {
//                    tmp.push_back({ q[i].first->left,q[i].second * 2 });
//                }
//                if (q[i].first->right)
//                {
//                    tmp.push_back({ q[i].first->right,q[i].second * 2 + 1 });
//                }
//            }
//            q = tmp;
//        }
//        return ret;
//    }
//};



// 在每个树行中找最大值
// https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
//class Solution {
//public:
//    vector<int> largestValues(TreeNode* root)
//    {
//        vector<int> ret;
//        if (root == nullptr)
//        {
//            return ret;
//        }
//        queue<TreeNode*> q;
//        q.push(root);
//        while (q.size())
//        {
//            int Max = INT_MIN;
//            int sz = q.size();
//            for (int i = 0; i < sz; i++)
//            {
//                TreeNode* t = q.front();
//                q.pop();
//                Max = max(Max, t->val);
//                if (t->left)
//                {
//                    q.push(t->left);
//                }
//                if (t->right)
//                {
//                    q.push(t->right);
//                }
//
//            }
//            ret.push_back(Max);
//        }
//        return ret;
//    }
//};


class KthLargest
{
    priority_queue<int, vector<int>, greater<int>> heap;
public:
    int r;
    KthLargest(int k, vector<int>& nums)
    {
        r = k;
        for (auto x : nums)
        {
            heap.push(x);
            if (heap.size() > k)
            {
                heap.pop();
            }
        }

    }
    int add(int val)
    {
        heap.push(val);
        if (heap.size() > r)
        {
            heap.pop();
        }
        return heap.top();
    }
};


// 最后一块石头的重量
// https://leetcode.cn/problems/last-stone-weight/
class Solution {
public:
    int lastStoneWeight(vector<int>& stones)
    {
        priority_queue<int, vector<int>> heap;
        int x, y;
        for (auto e : stones)
        {
            heap.push(e);
        }
        int sz = heap.size();
        while (heap.size() > 1)
        {
            x = heap.top();
            heap.pop();
            y = heap.top();
            heap.pop();
            if (x > y)
            {
                heap.push(x - y);
            }
        }
        return heap.size() == 0 ? 0 : heap.top();
    }
};





class Solution
{
    typedef pair<string, int> PSI;
    struct cmp
    {
        bool operator() (const PSI& a, const PSI& b)
        {
            if (a.second == b.second)
            {
                return a.first < b.first;
            }
            return a.second > b.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        map<string, int> hash;
        for (auto& s : words)
        {
            hash[s]++;
        }
        priority_queue<PSI, vector<PSI>, cmp> heap;
        for (auto& psi : hash)
        {
            heap.push(psi);
            if (heap.size() > k)
            {
                heap.pop();
            }
        }
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--)
        {
            ret[i] = heap.top().first;
            heap.pop();

        }
        return ret;
    }
};




// 数据流的中位数
// https://leetcode.cn/problems/find-median-from-data-stream/
class MedianFinder {
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;
public:
    MedianFinder() {

    }

    void addNum(int num)
    {
        if (left.size() == right.size())
        {
            if (left.empty() || num <= left.top())
            {
                left.push(num);
            }
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else {
            if (num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else
            {
                right.push(num);
            }
        }

    }

    double findMedian()
    {
        if (left.size() == right.size())
        {
            return (left.top() + right.top()) / 2.0;
        }
        return left.top();
    }
};



// 岛屿数量
// https://leetcode.cn/problems/number-of-islands/
class Solution
{
    typedef pair<int, int> PII;
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    bool vis[301][301];
    int m, n;
public:
    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({ i,j });
        vis[i][j] = true;
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x < m && x >= 0 && y < n && y >= 0 && !vis[x][y] && grid[x][y] == '1')
                {
                    q.push({ x,y });
                    vis[x][y] = true;
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        int count = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && !vis[i][j])
                {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;

    }
};


class Solution {
    int m, n;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    bool vis[51][51];
    typedef pair<int, int> PII;
public:
    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        int count = 1;
        queue<PII> q;
        q.push({ i,j });
        vis[i][j] = true;
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] &&
                    !vis[x][y])
                {
                    q.push({ x, y });
                    vis[x][y] = true;
                    count++;
                }
            }
        }
        return count;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j])
                {
                    ret = max(ret, bfs(grid, i, j));
                }
            }
        }
        return ret;
    }
};



class Solution
{
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int m, n;
    bool vis[100][100];

public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance)
    {
        m = maze.size(), n = maze[0].size();
        //memset(vis, 0, sizeof vis);
        queue<pair<int, int>> q;
        q.push({ entrance[0], entrance[1] });
        vis[entrance[0]][entrance[1]] = true;
        int step = 0;
        while (q.size())
        {
            step++;
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int j = 0; j < 4; j++)
                {
                    int x = a + dx[j], y = b + dy[j];
                    if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.'
                        && !vis[x][y])
                    {
                        // 判断是否已经到达出⼝
                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1)
                            return step;
                        q.push({ x, y });
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};





class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r * 2 - 2;
        int c = (n + t - 1) / t * (r - 1);
        vector<string> mat(r, string(c, 0));
        for (int i = 0, x = 0, y = 0; i < n; ++i) {
            mat[x][y] = s[i];
            if (i % t < r - 1) {
                ++x; // 向下移动
            }
            else {
                --x;
                ++y; // 向右上移动
            }
        }
        string ans;
        for (auto& row : mat) {
            for (char ch : row) {
                if (ch) {
                    ans += ch;
                }
            }
        }
        return ans;
    }
};


class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank)
    {
        map<string, int> hash;
        string change = "ACGT";
        if (startGene == endGene)
        {
            return 0;
        }
        for (auto e : bank)
        {
            hash[e] = 0;
        }
        if (!hash.count(endGene))
        {
            return -1;
        }
        queue<string> q;
        q.push(startGene);
        hash[startGene]++;
        int ret = 0;
        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                string t = q.front();
                q.pop();
                for (int i = 0; i < 8; i++)
                {
                    string tmp = t;
                    for (int j = 0; j < 4; j++)
                    {
                        tmp[i] = change[j];
                        if (hash.count(tmp) && !hash[tmp])
                        {
                            if (tmp == endGene) return ret;
                            q.push(tmp);
                            hash[tmp]++;
                        }
                    }
                }
            }
        }
        return -1;
    }
};




class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        map<string, int> hash;
        for (auto e : wordList)
        {
            hash[e] = 0;
        }
        if (!hash.count(endWord))
        {
            return 0;
        }
        queue<string> q;
        q.push(beginWord);
        hash[beginWord]++;
        int ret = 1;
        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                string t = q.front();
                q.pop();
                for (int i = 0; i < t.size(); i++)
                {
                    string tmp = t;
                    for (char ch = 'a'; ch <= 'z'; ch++)
                    {
                        tmp[i] = ch;
                        if (hash.count(tmp) && hash[tmp] == 0)
                        {
                            if (tmp == endWord)
                            {
                                return ret;
                            }
                            q.push(tmp);
                            hash[tmp]++;
                        }
                    }
                }
            }
        }
        return 0;
    }
};



class Solution {
    int m, n;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
public:
    int cutOffTree(vector<vector<int>>& forest)
    {
        if (f[0][0] == 0)
        {
            return -1
        }
        m = forest.size(), n = forest[0].size();
        vector<pair<int, pair<int, int>>> tree;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (f[i][j] > 1) {
                    tree.push_back(make_pair(f[i][j], make_pair(i, j)));
                }
            }
        }
        sort < tree.begin(), tree.end());
        int row = 0, col = 0;
        int step = 0;
        for (auto e : tree)
        {
            int count = bsf()
        }
        priority_queue<int, vector<int>, greater<int>> q;
        while (q.size())
        {

        }

    }
};





class Solution {

    int _m, _n;
public:
    int cutOffTree(vector<vector<int>>& forest)
    {
        int m = forest.size(), n = forest[0].size();
        _m = m, _n = n;
        vector<pair<int, int>> trees;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (forest[i][j] > 1) trees.push_back({ i, j });

        sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const
            pair<int, int>& p2)
            {
                return forest[p1.first][p1.second] < forest[p2.first][p2.second];
            });
        // 2. 按照顺序砍树
        int bx = 0, by = 0;
        int ret = 0;
        for (auto& [a, b] : trees)
        {
            int step = bfs(forest, bx, by, a, b);
            if (step == -1) return -1;
            ret += step;
            bx = a, by = b;
        }
        return ret;
    }

    bool vis[51][51];
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey)
    {
        if (bx == ex && by == ey) return 0;
        queue<pair<int, int>> q;
        memset(vis, 0, sizeof vis); // 清空之前的数据
        q.push({ bx, by });
        vis[bx][by] = true;
        int step = 0;
        while (q.size())
        {
            step++;
            int sz = q.size();
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && x < _m && y >= 0 && y < _n && f[x][y] && !vis[x]
                        [y])
                    {
                        if (x == ex && y == ey) return step;
                        q.push({ x, y });
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};



// https://leetcode.cn/problems/01-matrix/
class Solution {
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j] == 0)
                {
                    q.push({ i,j });
                    dist[i][j] = 0;
                }
            }
        }
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b] + 1;
                    q.push({ x,y });
                }
            }
        }
        return dist;
    }
};

// https://leetcode.cn/problems/number-of-enclaves/
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;
public:
    int numEnclaves(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j])
                {
                    q.push({ i,j });
                    vis[i][j] = true;

                }
            }
        }
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
                {
                    q.push({ x,y });
                    vis[x][y] = true;
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] && !vis[i][j])
                {
                    ret++;

                }
            }
        }
        return ret;
    }
};



// https://leetcode.cn/problems/map-of-highest-peak/
class Solution
{
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (isWater[i][j])
                {
                    q.push({ i, j });
                    dist[i][j] = 0;
                }
            }
        }
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
                {
                    q.push({ x,y });
                    dist[x][y] = dist[a][b] + 1;
                }
            }
        }
        return dist;
    }
};



// https://leetcode.cn/problems/as-far-from-land-as-possible/
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;
public:
    int maxDistance(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j])
                {
                    q.push({ i, j });
                    dist[i][j] = 0;
                }
            }
        }
        int ret = -1;
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
                {
                    q.push({ x,y });
                    dist[x][y] = dist[a][b] + 1;
                    ret = max(ret, dist[x][y]);
                }
            }
        }
        return ret;
    }
};



#include <unordered_map>
// https://leetcode.cn/problems/course-schedule/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<int> in(numCourses);
        unordered_map<int, vector<int>> edges;
        queue<int> q;
        for (auto& e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }
        for (int i = 0; i < numCourses; i++)
        {
            if (!in[i])
            {
                q.push(i);
            }
        }
        while (q.size())
        {
            int m = q.front();
            q.pop();
            for (auto e : edges[m])
            {
                in[e]--;
                if (!in[e])
                {
                    q.push(e);
                }
            }
        }
        for (auto e : in)
        {
            if (e)
            {
                return false;
            }
        }
        return true;
    }
};


class Solution
{

public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> edges;
        vector<int> in(numCourses);
        queue<int> q;
        for (auto& e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }
        for (int i = 0; i < numCourses; i++)
        {
            if (!in[i])
            {
                q.push(i);
            }
        }
        vector<int> ret;
        while (q.size())
        {
            int m = q.front();
            q.pop();
            ret.push_back(m);
            for (auto e : edges[m])
            {
                in[e]--;
                if (!in[e])
                {
                    q.push(e);
                }
            }
        }
        if (ret.size() == numCourses)
        {
            return ret;
        }
        return {};
    }
};